﻿//#define _CRT_SECURE_NO_WARNINGS
//
//
//// 给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
//// 现在，请你按照字典序将所有的排列方法输出。
// #include <iostream>
// #include <cstring>
// #include <algorithm>
// #include <vector>
// #include <unordered_map>
//
// using namespace std;
//
// int n;
// vector<vector<int>> ans;
// vector<int> path;
//
// void dfs(int u, vector<int> path, unordered_map<int, int> hash){
//     if(u == n){
//         ans.push_back(path);
//         return;
//     }
//
//     for(int i = 1; i <= n; i++)
//         if(hash[i] == 0){
//             hash[i]++;
//             path.push_back(i);
//             dfs(u + 1, path, hash);
//             path.pop_back();
//             hash[i]--;
//         }
// }
//
// int main(void){
//     cin >> n;
//
//     int u = 0;
//     unordered_map<int, int> hash;
//     dfs(u, path, hash);
//
//     for(int i = 0; i < ans.size(); i++){
//         for(int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << ' ';
//         cout << endl;
//     }
//
//     return 0;
// }
//
//
//
// // 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
//
//// 来源：力扣（LeetCode）
//// 链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
//// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
// class Solution {
// public:
//     vector<string> strs{ " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//     vector<string> ans;
//     void dfs(string digits, string str, int i) {
//         if (i == digits.size()) {
//             ans.push_back(str);
//             return;
//         }
//
//         int num = digits[i] - '0';
//         string s = strs[num];
//         for (int j = 0; j < s.size(); j++)
//             dfs(digits, str + s[j], i + 1);
//     }
//
//     vector<string> letterCombinations(string digits) {
//         if (digits.size() == 0) return ans;
//
//         string str;
//         int i = 0;
//         dfs(digits, str, i);
//
//         return ans;
//     }
// };
//
//
